
public class NumberOfPaths {
  public int numberOfPaths(int[][] grid, int k) {
    final int MOD = 1_000_000_007;
    int m = grid.length, n = grid[0].length;
    int[][][] dp = new int[m+1][n+1][k];
    dp[1][0][0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            for (int l = 0; l < k; l++) {
                int rem = (l + grid[i][j]) % k;
                dp[i + 1][j + 1][l] += (dp[i][j+1][rem] + dp[i+1][j][rem]) % MOD;
            }
        }
    }

        return dp[m - 1][n - 1][0];
  }


//   class Solution {
//     public int numberOfPaths(int[][] grid, int k) {
//         final int MOD = 1_000_000_007;
//         int m = grid.length;
//         int n = grid[0].length;
//         int[][][] f = new int[m + 1][n + 1][k];
//         f[1][0][0] = 1;
//         for (int i = 0; i < m; i++) {
//             for (int j = 0; j < n; j++) {
//                 for (int s = 0; s < k; s++) {
//                     int newS = (s + grid[i][j]) % k;
//                     f[i + 1][j + 1][newS] = (f[i][j + 1][s] + f[i + 1][j][s]) % MOD;
//                 }
//             }
//         }
//         return f[m][n][0];
//     }
// }




  public static void main(String[] args) { 
  }
}
